import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

public class Sort {
    /**
     * 插入排序
     * 时间复杂度O（n^2）
     * 稳定
     * 从无序中拿一个插入到有序中
     * @param array
     */
    public static void InsertSort(int[] array) {   //1.插入排序
        for (int i = 1; i < array.length ; i++) {
            int tmp = array[i];
            int j = i-1;
            for (j = i-1;j >= 0 ;j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];  //就把j往后放
                } else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    public static void InsertSort1(int[] array,int end,int start) {   //快排优化
        for (int i = 1; i <= end ; i++) {
            int tmp = array[i];
            int j = i-1;
            for (j = i-1;j >= start;j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                } else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    /**
     * 希尔排序（是插入排序的优化）
     * 时间复杂度O（n^1.3）到O（n^1.5）
     * 不稳定
     * @param array
     */
    public static void ShellSort(int[] array) {   //2.希尔排序
        int gap = array.length;
        while(gap > 1) {
            shell(array,gap);
            gap = gap/2;
        }
        shell(array,1);
    }
    public static void shell(int[] array,int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (j = i-gap; j >= 0 ; j = j-gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                } else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    /**
     * 选择排序
     * 时间复杂度O（n^2）
     * 不稳定
     * @param array
     */
    public static void SelectSort(int[] array) {        //3.选择排序
        for (int i = 0; i < array.length; i++) {
            for (int j = i+1; j < array.length; j++) {
                if(array[i] >= array[j]) {
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }
    public static void SelectSort1(int[] array) {    //选择排序优化
        for (int i = 0; i < array.length-1; i++) {
            int min = i;
            //找到最小值，中途不交换
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[min]) {
                    min = j;
                }
            }
            if(array[i] > array[min]) {
                int tmp = array[i];
                array[i] = array[min];
                array[min] = tmp;
            }
        }
    }
    public static void swap(int[] array,int a,int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    /**
     * 堆排序
     * 时间复杂度O（N*logn）
     * 快速排序为啥比堆排快，应为快排前面的k值比较小些
     * 空间复杂度O(1)
     * 不稳定
     * @param array
     */
    public static void HeapSort(int[] array) {
        //1.建堆，升序用大堆
        CreatHeap(array);
        //2.交换然后调整
        int end = array.length-1;
        while (end>0) {
            swap(array,0,end);
            ShiftDown(array,0,end);
            end--;
        }
    }
    public static void CreatHeap(int[] array) {
        for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
            ShiftDown(array,parent,array.length);
        }
    }
    public static void ShiftDown(int[] array,int parent,int len) {
        int child = parent*2+1;
        while(child < len){
            if(child+1 < len && array[child] < array[child+1]) {
                child++;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }

    /**
     * 冒泡排序
     * 时间复杂度O(n^2)
     * 空间O(1)
     * 稳定
     * @param array
     */
    public static void BubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                }
            }
        }
    }
    public static void BubbleSort1(int[] array) {
        for (int i = 0; i < array.length; i++) {          //i代表趟数
            boolean flg = true;
            for (int j = 0; j < array.length-1-i; j++) {                //j代表走到哪停下来
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flg = false;
                }
            }
            if(flg) {
                break;
            }
        }
    }

    /**
     * 快速排序
     * 时间复杂度最好O（N*logn）
     * 最差O（n^2）（没有优化的情况，且有序）
     * 空间复杂度O（logn）
     * 空间复杂度最差O(N)（变成单链表的时候）
     * 不稳定
     * @param array
     */
    public static void QuickSort(int[] array) {
        Quick(array,0, array.length-1);
    }
    public static void Quick(int[] array,int left,int right) {
        if(left >= right) {   //递归结束（大于说明没有了左数，基数减一会导致right会小于left）（重点）
            return;
        }
        if(right - left + 1 <=14000){                    //当区间越来越小，采用直接插入排序优化，越来越小说明越来越有序，直接插入越有序越快
            InsertSort1(array, left, right);
            return;
        }
        int midmaxIndex = findmidmaxIndex(array,left,right);  //三数取中法，避免有序数组深度太深栈溢出，
        swap(array,midmaxIndex,left);
        int partition = quickfun(array,left,right);
        Quick(array,left,partition-1);
        Quick(array,partition+1,right);
    }
    public static int findmidmaxIndex(int[] array,int left,int right) {
        int mid = left + ((right - left) >>> 1);
        if (array[left] > array[right]) {   //左大于右
            if (array[mid] > array[left]) {    //中大于左
                return left;    //左居中
            } else if (array[mid] > array[right]) {   //中大于右
                return mid;   //中居中
            } else {
                return right;   //右居中
            }
        } else {   //右大于左
                if (array[mid] > array[right]) {   //中大于右
                    return right;  //右居中
                } else if (array[mid] > array[left]) {   //中大于左
                    return mid;   //中居中
                } else {
                    return left;  //左居中
                }
        }
    }
    public static int quickfun(int[] array,int start,int end) {     //挖坑法找基准值
        int tmp = array[start];
        while(start < end) {
            while(start < end && array[end] >= tmp) {              //等于也要--，否则当相等时会出现死循环
                end--;
            }
            array[start] = array[end];
            while (start < end && array[start] <= tmp) {
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;
    }
    public static void QuickSort1(int[] array) {                 //非递归实现快排，用栈
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int pivot = quickfun(array,left,right);
        if(left+1 < pivot) {
            stack.push(left);
            stack.push(pivot-1);
        }
        if(right-1 > pivot) {
            stack.push(pivot+1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = quickfun(array,left,right);
            if(left+1 < pivot) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(right-1 > pivot) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

    /**
     * 归并排序
     * 时间复杂度O（N*logN）
     * 空间复杂度O（N）
     * 稳定排序
     * @param array
     */
    public static void MergeSort(int[] array) {
        mergeSort(array,0,array.length-1);
    }
    private static void mergeSort(int[] array,int low,int high) {
        if(low == high) {
            return;
        }
        int mid = low + ((high-low)>>>1);
        mergeSort(array,low,mid);
        mergeSort(array,mid+1,high);
        mergehelp(array,low,mid,high);
    }
    private static void mergehelp(int[] array,int low,int mid,int high) {  //二路归并
        int s1 = low;
        int s2 = mid+1;
        int e1 = mid;
        int e2 = high;
        int[] newarray = new int[high-low+1];
        for (int i = 0; i < high-low+1; i++) {
            if(s1 > e1) {
                newarray[i] = array[s2];
                s2++;
                continue;
            }
            if(s2 > e2) {
                newarray[i] = array[s1];
                s1++;
                continue;
            }
            if(array[s1] <= array[s2]) {
                newarray[i] = array[s1];
                s1++;
            }else {
                newarray[i] = array[s2];
                s2++;
            }
        }
        for (int i = 0; i < high-low+1; i++) {
            array[i+low] = newarray[i];   //赋值时考虑区间
        }
    }

    public static void MergeSort1(int[] array) {  //归并排序非递归（一组归并，两组归并，八组归并，直到组数不小于数组长度即可）
        int nums = 1;
        while (nums < array.length) {
            for (int i = 0; i < array.length; i += nums*2) {
                int left = i;
                int mid = left+nums-1;
                if(mid >= array.length) {  //防止越界
                    mid = array.length-1;
                }
                int right = mid+nums;
                if(right >= array.length) {  //防止越界
                    right = array.length-1;
                }
                mergehelp(array,left,mid,right);
            }
            nums = nums*2;
        }
    }

    /**
     * 计数排序
     * 时间复杂度O（N）
     * 空间复杂度O（M）M为数据最大值减数组最小值范围
     * 不稳定，但是也可以稳定（从后往前遍历，在计数数组中减一）
     * @param array
     */
    public static void CountingSort(int[] array) {
        int max = array[0];
        int min = array[0];
        //1.先找到最大值和最小值确定范围
        for (int i = 1; i < array.length; i++) {
            if(array[i] > max) {
                max = array[i];
            }
            if(array[i] < min) {
                min = array[i];
            }
        }
        //2.定义范围大小的空间，且开始计数
        int[] newarray = new int[max-min+1];
        for (int i = 0; i < array.length; i++) {
            int index = array[i];
            newarray[index-min]++;
        }
        //3.遍历计数数组，逐一覆盖原数组
        int index = 0;
        for (int i = 0; i < newarray.length; i++) {
            while (newarray[i] > 0) {
                array[index] = i+min;
                index++;
                newarray[i]--;
            }
        }
    }

    public static void test1(int a) {
        int[] array = new int[a];
        for (int i = 0; i < a; i++) {
            array[i] = i;
        }
        long start = System.currentTimeMillis();
        //InsertSort(array);
        //ShellSort(array);
        //SelectSort(array);
        //BubbleSort(array);
        //QuickSort(array);
        //mergeSort(array);
        HeapSort(array);
        long end = System.currentTimeMillis();
        System.out.println(end-start);
    }
    public static void test2(int a) {
        int[] array = new int[a];
        Random random = new Random();
        for (int i = 0; i < a; i++) {
            array[i] = random.nextInt(a);
        }
        long start = System.currentTimeMillis();
        //InsertSort(array);
        //ShellSort(array);
        //SelectSort1(array);
        //BubbleSort1(array);
        //QuickSort(array);
        //mergeSort(array);
        HeapSort(array);
        long end = System.currentTimeMillis();
        System.out.println(end-start);
    }

    public static void main(String[] args) {
        int[] nums1 = {0,1,2,3,4,5,11,7,8,9};
        //QuickSort1(nums1);
        //BubbleSort(nums1);
        //MergeSort1(nums1);
        //CountingSort(nums1);
        MergeSort(nums1);
        System.out.println(Arrays.toString(nums1));
    }
    public static void main4(String[] args) {
        int[] nums1 = {0,1,2,3,4,5,11,7,8,9};
        HeapSort(nums1);
        System.out.println(Arrays.toString(nums1));
    }

    public static void main3(String[] args) {
        test1(1000_0000);
        test2(1000_0000);
    }

    public static void main2(String[] args) {
        int[] muns1 = {0,1,2,3,4,5,11,7,8,9};
        long start = System.currentTimeMillis();
        SelectSort1(muns1);
        long end = System.currentTimeMillis();
        System.out.println(end-start);
        System.out.println(Arrays.toString(muns1));
    }
    public static void main1(String[] args) {
        int[] muns1 = {0,1,2,3,4,5,11,7,8,9};
        InsertSort(muns1);
        System.out.println(Arrays.toString(muns1));
    }
}
